package com.zjb.datastructure.sort;

public class QuickSort {

   static int partition(int[] nums,int start,int end) {

        int pivot = nums[end];
        int j = start;
        for (int i = start; i < end; i++) {
            if (nums[i] < pivot ) {
                if (i != j) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
                j++;
            }
        }
        nums[end ] = nums[j];
        nums[j] = pivot;
        return j;
    }

    static void sort(int[] nums) {


        quickSort(nums, 0, nums.length-1);

    }

    static void quickSort(int[] nums,int start,int end) {

        if (start > end) {
            return;
        }
        int partition = partition(nums, start, end);
        quickSort(nums, start, partition-1);
        quickSort(nums, partition+1, end);
    }

    public static void main(String[] args) {
        int[] b = {5,1,3,4,2,4,5,6};
        sort(b);
        for (int i : b) {
            System.out.print(i);
        }
    }
}
